The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (usually routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. Because each node has a common LSDB (other than when advertised changes are propagating around the network) any node is able to compute the spanning tree rooted at any other node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network, each node sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node (the “first node”), the first node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth.
As a result synchronization of a data communications network is extremely important. One particular type of network change where synchronization can be burdensome is when a new node enters the network for example by manual intervention or as part of a MANET (Mobile Ad hoc Network).
A known synchronization technique for a node entering a network is described in the Intermediate System-Intermediate System (IS-IS) protocol which is described in International Standard ISO/IIEC 10589 2002 clause 7.3. This can be understood referring to FIG. 1, which depicts an illustrative network diagram showing a conventional technique for synchronizing a data communications network. A network designated generally 10 comprises a plurality of nodes N1, N2, N3, N4 termed here “existing nodes” which are joined by respective links 12, 14, 16. A node N0, termed here the “entering node” enters the network 10 for example by coming into range of nodes in the network and forms links, say, with each of nodes N1 to N4 via respective links 18, 20, 22 and 24. It will be seen, as a result, that the network has changed and hence that the LSDBs of all of the nodes N0 to N4 need to be updated and synchronized.
FIG. 2 depicts a schematic diagram of an LSDB maintained at a node in the network. For illustrative purposes the LSDB of node N1 is shown but it will be appreciated that LSDBs are maintained at all other nodes as well. The LSDB is designated generally 210 and includes a first, data column 212 containing the LSPs: LSP1, LSP2, LSP3 and LSP4 of each existing node on the network prior to synchronization. The LSDB also contains a second, send routing message (SRM) flag column 214 in which a flag value is set against each LSP to indicate when synchronization is required. In the case of node N1 only a single SRM column is required as there is only a single interface, to node N2. However where a node has multiple interfaces then multiple respective SRM columns are used.
In the case of the entering node N0 the LSDB will have only one entry: its LSP, but on entry to the network and prior to synchronization, four SRM columns, one for each of the interfaces to the existing nodes in the network 210.
On entry into the network the entering node N0 exchanges hello messages with each of the existing nodes N1 to N4 and all SRM flags are set to 1 as a result of which each node sends the contents of its LSDB including all LSPs down the newly created interface. Upon receipt of each LSP the receiving node sends an acknowledgement message; if the acknowledgement message is not received then the SRM flag is not reset and the LSPs are resent until all nodes have all information and are synchronized. Where nodes N1 to N4 in fact form part of a larger network but are the only neighbor nodes to N0 then it can be assumed that nodes N1 to N4 are synchronized with the remainder of the network and will flood node N0's LSP throughout the network ensuring convergence of all nodes on a synchronized LSDB.
According to the conventional system the acknowledgment of receipt of an LSP is effected through the medium of a partial sequence number packet (psnp) which returns the contents of one or more LSP headers that have been received allowing multiple SRM flags to be reset to zero. In a further optimization to the conventional technique the acknowledgement takes the form of a complete sequence number packet (csnp) which is sent containing the header of all LSPs in the LSDB allowing synchronization to be completed by addressing any discrepancies between the csnp and the contents of the LSDB of a node receiving the csnp.
A problem with known approaches to synchronization lies in the duplication of information. In the approach described above node N0 synchronizes with each of nodes N1 to N4, but nodes N1 to N4 are already synchronized with one another by virtue of sharing the same network. As a result redundant information is swapped between the entering node and the existing nodes which can add to the cost of the operation.
This is particularly significant, in a mobile network such as MANET which is described in “Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations” by S. Corson, J Macker, which is available at the time of writing on the file “rfc2501.txt” in the directory “rfc” of the domain “ietf.org” of the World Wide Web. Mobile ad hoc networking refers to networks in which nodes enter and leave regularly. For example, mobile ad hoc networking is encountered when wireless network devices come and go from within proximity to a wireless access point. Firstly by virtue of the mobility of the network elements, nodes will enter and leave the mobile network very quickly meaning that sequence synchronization is required. Furthermore it is desirable to reduce power consumption as far as possible on mobile devices and hence reduce the transmission data to a minimum. This is especially the case as mobile devices commonly have very low bandwidth.
However merely synchronizing with one existing node will give rise to problems if the entering node is in fact synchronizing with multiple independent synchronization domains, that is, the entering node enters a network having two sub-networks independent of each other.